`
https://leetcode.cn/problems/minimize-malware-spread/
`

/**
 * @param {number[][]} graph
 * @param {number[]} initial
 * @return {number}
 */
var minMalwareSpread = function (graph, initial) {
  const n = graph.length
  const uf = new UnionFind(n)
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      graph[i][j] && uf.connect(i, j)
    }
  }
  // 此时每个连通分量有三种情况
  // 1. 没有节点被感染
  // 2. 只有一个节点被感染
  // 3. 有多个节点被感染
  // 由于只能去掉一个节点的感染，所以只有第 2 种情况需要考虑
  let res = n, maxReduce = 0
  // 计算连通分量里有多少个感染节点
  const count = new Array(n).fill(0)
  for (const x of initial) {
    count[uf.find(x)]++
  }

  for (const x of initial) {
    const root = uf.find(x)
    // 如果 x 所在连通分量里只有一个被感染的节点
    if (count[root] === 1) {
      const infectSize = uf.componentSizeOf(x)
      // 如果能减少更多的感染节点，或下标更靠前，更新答案
      if (infectSize > maxReduce || (infectSize === maxReduce && x < res)) {
        res = x
        maxReduce = infectSize
      }
    }
  }
  return res === n ? Math.min(...initial) : res
};

/**
 * 并查集（Union-Find）算法
 */
class UnionFind {
  // n 为图中节点的个数
  constructor(n) {
    // 连通分量个数
    this._count = n
    // 存储每个节点的父节点
    this.parent = Array.from({ length: n }, (_, index) => index)
    // 存储每个节点的权重（以该节点为根的树中节点个数）
    this.size = new Array(n).fill(1)
  }

  // 将节点 p 和节点 q 连通
  connect(p, q) {
    const rootP = this.find(p)
    const rootQ = this.find(q)

    if (rootP === rootQ) {
      return false
    }

    // 小树接到大树下面，较平衡
    if (this.size[rootP] < this.size[rootQ]) {
      this.parent[rootP] = rootQ
      this.size[rootQ] += this.size[rootP]
    } else {
      this.parent[rootQ] = rootP
      this.size[rootP] += this.size[rootQ]
    }
    // 两个连通分量合并成一个连通分量
    this._count--
    return true
  }

  // 判断节点 p 和节点 q 是否连通
  isConnected(p, q) {
    const rootP = this.find(p)
    const rootQ = this.find(q)
    return rootP === rootQ
  }

  // 返回图中的连通分量个数
  count() {
    return this._count
  }

  // 返回 x 所在的连通分量的大小
  componentSizeOf(x) {
    const rootX = this.find(x)
    return this.size[rootX]
  }

  // 返回节点 x 的根节点
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x])
    }
    return this.parent[x]
  }
}